// 时间复杂度: 平均O(n1.3)
// 空间复杂度: O(1)
// 稳定性: 稳定排序

class ShellSort {
public:
    static void shellSort(int *array, int length) {
        for (int gap = length / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < length; i++) {
                int j = i;
                int current = array[j];
                while (0 <= j - gap && current < array[j - gap]) {
                    array[j] = array[j - gap];
                    j -= gap;
                }
                array[j] = current;
            }
        }
    }
};